package uestc.lj.advanced.dp;

/**
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code12_BurstBalloons {

	public static int maxCoins1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		if (arr.length == 1) {
			return arr[0];
		}
		int length = arr.length;
		//   3 2 5
		//   0 1 2
		// 等价替换
		// 1 3 2 5 1
		// 0 1 2 3 4
		int[] help = new int[length + 2];
		help[0] = 1;
		help[length + 1] = 1;
		System.arraycopy(arr, 0, help, 1, length);
		return process(help, 1, length);
	}

	/**
	 * arr[left...right]范围上所有气球都被打爆的最大分数
	 * 假设arr[left-1]和arr[right+1]一定没有被打爆
	 * 贪心策略为每一个气球都被最后打爆
	 *
	 * @param arr   气球分数数组
	 * @param left  左边界
	 * @param right 右边界
	 * @return 最大分数
	 */
	private static int process(int[] arr, int left, int right) {
		if (left == right) {
			// arr[left...right]范围上只有一个气球，直接打爆即可
			return arr[left - 1] * arr[left] * arr[right + 1];
		}

		//最后打爆arr[left]和最后打爆arr[right]的方案比较一下
		int max = Math.max(
				arr[left - 1] * arr[left] * arr[right + 1] + process(arr, left + 1, right),
				arr[left - 1] * arr[right] * arr[right + 1] + process(arr, left, right - 1));

		// 尝试中间位置的气球最后被打爆的每一种方案
		for (int i = left + 1; i < right; i++) {
			max = Math.max(max,
					arr[left - 1] * arr[i] * arr[right + 1] + process(arr, left, i - 1) + process(arr, i + 1, right));
		}
		return max;
	}

	public static int maxCoins2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		if (arr.length == 1) {
			return arr[0];
		}
		int N = arr.length;
		int[] help = new int[N + 2];
		help[0] = 1;
		help[N + 1] = 1;
		System.arraycopy(arr, 0, help, 1, N);

		int[][] dp = new int[N + 2][N + 2];
		for (int i = 1; i <= N; i++) {
			dp[i][i] = help[i - 1] * help[i] * help[i + 1];
		}

		for (int L = N; L >= 1; L--) {
			for (int R = L + 1; R <= N; R++) {
				// 求解dp[L][R]，表示help[L..R]上打爆所有气球的最大分数
				// 最后打爆help[L]的方案
				int finalL = help[L - 1] * help[L] * help[R + 1] + dp[L + 1][R];
				// 最后打爆help[R]的方案
				int finalR = help[L - 1] * help[R] * help[R + 1] + dp[L][R - 1];
				// 最后打爆help[L]的方案，和最后打爆help[R]的方案，先比较一下
				dp[L][R] = Math.max(finalL, finalR);
				// 尝试中间位置的气球最后被打爆的每一种方案
				for (int i = L + 1; i < R; i++) {
					dp[L][R] = Math.max(
							dp[L][R],
							help[L - 1] * help[i] * help[R + 1] + dp[L][i - 1] + dp[i + 1][R]);
				}
			}
		}
		return dp[1][N];
	}

	public static void main(String[] args) {
		int[] arr = {4, 2, 3, 5, 1, 6};
		System.out.println(maxCoins1(arr));
		System.out.println(maxCoins2(arr));
	}

}
